package heap;

import java.util.Comparator;
import java.util.Objects;

/**
 * @Author kaho
 * @create 2020/11/24
 */
public class BinaryHeap<E> extends AbstractHeap<E> {
    E[] arr;
    private static final int CAPACITY = 16;

    public BinaryHeap(E[] arr) {
        this(null, arr);
    }

    public BinaryHeap(Comparator<E> comparator, E[] arr) {
        super(comparator);
        if(arr==null || arr.length==0){
            this.arr = (E[]) new Object[CAPACITY];
        }else {
            size = arr.length;
            int capacity = Math.max(CAPACITY, arr.length);
            this.arr =  (E[]) new Object[capacity];
            for (int i = 0; i < arr.length; i++) {
                this.arr[i] = arr[i];
            }
            for (int i = (size >> 2) - 1; i >= 0; i--) {
                siftDown(i);
            }
        }
    }

    public BinaryHeap(Comparator<E> comparator) {
        super(comparator);
        this.arr = (E[]) new Object[CAPACITY];

    }

    public BinaryHeap() {
        this(null, null);
    }


    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element is null.");
        }
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = arr.length;
        if (oldCapacity >= capacity) {
            return;
        }
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] elements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            elements[i] = arr[i];
        }
        arr = elements;
    }


    @Override
    public void clear() {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        arr[size++] = element;
        siftUp(size);
    }

    @Override
    public E get() {
        emptyCheck();
        return arr[0];
    }

    @Override
    public E remove() {
        emptyCheck();
        E e = arr[0];
        int lastIdx = --size;
        E down = arr[lastIdx];
        arr[0] = down;
        arr[lastIdx] = null;
        siftDown(0);

        return e;
    }

    private void siftDown(int idx) {
        if (idx> size -1) {
            return;
        }
        E e = arr[idx];

        int half = size >> 1;
        while (half > idx) {
            int childIdx = idx << 1 + 1;
            E child = arr[childIdx];

            int rightIdx = childIdx + 1;
            if (rightIdx <size && compare(arr[rightIdx], child)>0){
                child = arr[childIdx = rightIdx];
            }

            if (compare(e, child)>=0){
                break;
            }
            arr[idx] = child;
            idx = childIdx;
        }
        arr[idx] = e;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        if (size == 0) {
            arr[0] = element;
            size++;
            return null;
        }
        E e = arr[0];
        arr[0] = element;
        siftDown(0);
        return e;
    }

    /**
     * 让idx位置的元素上虑
     *
     * @param idx
     */
    public void siftUp(int idx) {
        E e = arr[idx];
        while (idx > 0) {
            int parentIdx = (idx - 1) >> 1;
            E parent = arr[parentIdx];
            if (compare(parent, e) >= 0) {
                break;
            }
            arr[idx] = parent;
            idx = parentIdx;
        }
        arr[idx] = e;
    }

    public Integer left(int i) {
        int lIdx = (i >> 1) + 1;
        return lIdx > size ? null : lIdx;
    }

    public Integer right(int i) {
        int rIdx = (i >> 1) + 2;
        return rIdx > size ? null : rIdx;
    }
}
